#!/usr/bin/python
# Write Python 3 code in this online editor and run it.
def Merge(a, start, mid, end):
	tmp = []
	L = start
	r = mid + 1
	while L <= mid and r <= end:
		if a[L] <= a[r]:
			tmp.append(a[L])
			L += 1
		else:
			tmp.append(a[r])
			r +=1
	print(a[L:mid + 1])
	print(a[r:end + 1])
	#tmp.append(a[L:mid + 1]) #[3]
	#tmp.append(a[r:end + 1]) #[]
	tmp.extend(a[L:mid + 1])
	tmp.extend(a[r:end + 1])
	for i in range(start,end+1):
		a[i] = tmp[i-start]
	print(start, end, a) #0 1 [2, [3], []]

def MergeSort(a, start, end):
	if start == end:
		return
	mid = (start + end) // 2
	MergeSort(a, start, mid)
	MergeSort(a, mid+1, end)
	Merge(a, start, mid, end)
	
if __name__ == '__main__':
	a = [8, 7, 6, 5, 4, 3, 2, 1]
	MergeSort(a, 0, 7)
	
'''
[8]
[]
0 1 [7, 8, 6, 5, 4, 3, 2, 1]
[6]
[]
2 3 [7, 8, 5, 6, 4, 3, 2, 1]
[7, 8]
[]
0 3 [5, 6, 7, 8, 4, 3, 2, 1]
[4]
[]
4 5 [5, 6, 7, 8, 3, 4, 2, 1]
[2]
[]
6 7 [5, 6, 7, 8, 3, 4, 1, 2]
[3, 4]
[]
4 7 [5, 6, 7, 8, 1, 2, 3, 4]
[5, 6, 7, 8]
[]
0 7 [1, 2, 3, 4, 5, 6, 7, 8]
'''